package com.zk.algorithm.backtracking;

import com.zk.algorithm.annotation.CrackingTheCodingInterview6;

/**
 * 填充颜色，将黑色填充为红色，所有周边的黑色像素点都要变
 *
 * @author zk
 */
@CrackingTheCodingInterview6("8.10")
public class PaintFill {

    enum Color { Black, White, Red, Yellow, Green }

    boolean paintFill(Color[][] screen, int r, int c, Color ncolor) {
        if (screen[r][c] == ncolor)
            return false;

        return paintFill(screen, r, c, screen[r][c], ncolor);
    }

    // 深度优先搜索
    boolean paintFill(Color[][] screen, int r, int c, Color ocolor, Color ncolor) {
        if (r < 0 || r >= screen.length || c < 0 || c >= screen[0].length) {
            return false;
        }

        if (screen[r][c] == ocolor) {
            screen[r][c] = ncolor;
            paintFill(screen, r - 1, c, ocolor, ncolor); // up
            paintFill(screen, r + 1, c, ocolor, ncolor); // down
            paintFill(screen, r, c - 1, ocolor, ncolor); // left
            paintFill(screen, r, c + 1, ocolor, ncolor); // right
        }

        return true;
    }

}
